package heap;

import java.util.Arrays;
import java.util.stream.Stream;

public class HeapSort {
    public static void sort(Comparable[] source) {
        Comparable[] heap = new Comparable[source.length + 1];
        // 构造队
        createHeap(source, heap);
        // 排序堆
        int N = heap.length - 1;
        while (N > 1) {
            // 交换首尾
            exchange(heap, 1, N);
            N--;
            // 在0-N的范围下沉
            sink(heap, 1, N);
        }
        // 将有序数组复制会 source
        System.arraycopy(heap, 1, source, 0, source.length);
    }

    private static void createHeap(Comparable[] source, Comparable[] heap) {
        System.arraycopy(source, 0, heap, 1, source.length);
        // 从堆的一半开始索引 对前一半元素执行下沉
        for (int i = (heap.length - 1) / 2; i > 0; i--) {
            sink(heap, i, heap.length - 1);
        }
    }

    /**
     * 下沉
     */
    private static void sink(Comparable[] heap, int k, int n) {
        while (k * 2 + 1 <= n) {
            int max = k;
            if (k * 2 + 1 <= n) {
                // 有右
                if (less(heap, k * 2, k * 2 + 1)) {
                    max = k * 2 + 1;
                } else {
                    max = k * 2;
                }
            }
            if (less(heap, max, k)) {
                // 如果当前大于所有子 则beak
                break;
            }
            exchange(heap, max, k);
            k = max;
        }
    }

    private static void exchange(Comparable[] heap, int x, int y) {
        Comparable temp = heap[x];
        heap[x] = heap[y];
        heap[y] = temp;
    }

    private static boolean less(Comparable[] heap, int x, int y) {
        return heap[x].compareTo(heap[y]) < 0;
    }

    public static void main(String[] args) {
        String[] arr = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
        HeapSort.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
